package com.cn.codebrush.leetcode.editor.cn;
// 2022-09-20 16:13:07
// 698  划分为k个相等的子集
//给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。 
//
// 
//
// 示例 1： 
//
// 
//输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
//输出： True
//说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。 
//
// 示例 2: 
//
// 
//输入: nums = [1,2,3,4], k = 3
//输出: false 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= len(nums) <= 16 
// 0 < nums[i] < 10000 
// 每个元素的频率在 [1,4] 范围内 
// 
// Related Topics 位运算 记忆化搜索 数组 动态规划 回溯 状态压缩 
// 👍 766 👎 0


import java.util.Arrays;

public class PartitionToKEqualSumSubsets{

public static void main(String[] args) {

Solution solution = new PartitionToKEqualSumSubsets().new Solution();

}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0, avg, n = nums.length;
        for (int stick : nums) sum += stick;
        if (sum % k != 0) return false;
        avg = sum / k;
        int[] dp = new int[1 << n]; // i状态下是否（可以继续放）可能可行
        Arrays.sort(nums);
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 0; i < 1 << n; i++) {
            if (dp[i] < 0) continue; // 还未更新值，-1表示不能继续放
            for (int j = 0; j < n && dp[i] + nums[j] <= avg; j++) {
                if ((i & (1 << j)) == 1) continue;
                int state = i | (1 << j);
                if (dp[state] < 0) { // 当s状态下还未更新值
                    dp[state] = (dp[i] + nums[j]) % avg;
                }
            }
        }
        return dp[(1 << n) - 1] == 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}